import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Try {

    List<List<String>> ret = new ArrayList<>();
    List<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        //还是就是回溯算符
        //就是逐个分隔
        //结果就在叶子结点中
        backTracking(s, 0);
        return ret;
    }

    private void backTracking(String s, int startIndex) {
        if (startIndex == s.length()) {
            String tmp = path.toString();
            //这里没有判断是否为回文串
            ret.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            //这里的分割线就是startIndex
            //我们直接在这里判断
            //范围为 startIndex ~ i
            //为了提高效率，我们边递归边验证回文串
            String tmp = s.substring(startIndex, i + 1);
            if (isPalindrome(tmp)) {
                path.add(tmp);
                //继续递归
                backTracking(s, i + 1);
                path.remove(path.size() - 1);
            } else {
                continue;
            }
        }
    }

    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i < j) {
            char a = s.charAt(i);
            char b = s.charAt(j);
            if (a == b) {
                i++;
                j--;
            } else {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        String tmp = list.toString();
        List<String> list1 = new ArrayList<>();
        list1.add("abc");
        list1.add("cde");
        List<String> list2 = new ArrayList<>();
        list2.add("ddd");
        list2.add("ccc");
        List<List<String>> res = new ArrayList<>();
        res.add(new ArrayList<>(list1));
        res.add(new ArrayList<>(list2));
        System.out.println(list1.toString());
        System.out.println(res.toString());

        System.out.println();
    }
    public static void main1(String[] args) {
        Test tree = new Test();
        Test.TreeNode root = Test.createTree();
        Test.prevOrderNor(root);
        System.out.println();
        Test.inOrderNor(root);
        System.out.println();
        Test.levelOrder(root);
        System.out.println();
        Test.postOrder(root);
    }
}
